package 单周赛.history;

import java.util.Arrays;

/**
 *
 */
public class 第294场单周赛 {

    public static void main(String[] args) {

        int[] capacity = {10, 2, 2};
        int[] rocks = {2, 2, 0};
        System.out.println(maximumBags(capacity, rocks, 100));

        int[][] stockPrices = {{1, 7}, {2, 6}, {3, 5}, {4, 4}, {5, 4}, {6, 3}};
        int[][] stockPrices2 = {{1, 7}, {2, 6}, {3, 5}, {4, 4}, {5, 4}, {6, 3}, {7, 2}, {8, 1}};
        System.out.println(minimumLines(stockPrices2));

    }

    /**
     * 统计letter出现的次数
     *
     * @param s
     * @param letter
     * @return
     */
    public int percentageLetter(String s, char letter) {
        double count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == letter) count++;
        }

        return (int) (count / s.length() * 100);
    }

    /**
     * 贪心思想
     * 将每个背包需要多少个石头记录下来，根据需要石头数量排序
     * 优先将石头放进需要 较少石头 可以凑满背包的背包
     *
     * @param capacity
     * @param rocks
     * @param additionalRocks
     * @return
     */
    public static int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[] realCapacity = new int[capacity.length];
        for (int i = 0; i < realCapacity.length; i++) {
            realCapacity[i] = capacity[i] - rocks[i];
        }
        Arrays.sort(realCapacity);
        int count = 0;
        for (int i = 0; i < realCapacity.length; i++) {
            if (realCapacity[i] == 0) {
                count++;
                continue;
            }
            if (additionalRocks >= realCapacity[i]) {
                count++;
                additionalRocks -= realCapacity[i];
            }

        }
        return count;
    }

    /**
     * 数学+贪心+排序
     * 将点按照 x 轴从小到大排序好，通过斜率来判断 三个点 是否可以连成线
     * 注意: 除法可能有误差，改成乘法判断
     * (y2-y1)*(x3-x2) == (x2-x1)*(y3-y2)
     *
     * @param stockPrices
     * @return
     */
    public static int minimumLines(int[][] stockPrices) {
        if (stockPrices.length == 2) {
            return 1;
        }
        Arrays.sort(stockPrices, (o1, o2) -> o1[0] - o2[0]);
        int left = 2, count = 0;
        while (left < stockPrices.length) {
            int x1 = stockPrices[left - 2][0];
            int y1 = stockPrices[left - 2][1];
            int x2 = stockPrices[left - 1][0];
            int y2 = stockPrices[left - 1][1];
            int right = left;
            while (right < stockPrices.length && (x2 - x1) * (stockPrices[right][1] - y2)
                    == (y2 - y1) * (stockPrices[right][0] - x2)) {
                right++;
            }
            count++;
            left = right + 1;
            // 注意: 需要特判倒数第一个拐点，最后一段只有两个点时
            if (left == stockPrices.length) count++;
        }
        return count;
    }

}
